package lhc.alg.top100;

/**
 * description: 这不跟53题一样嘛 刷烂了 滑动窗口整不了 数学归纳法行不通 动归搞 最后再来个状态压缩
 * 以 nums[i] 为结尾的「最大子数组和」为 dp[i]
 * dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。在这里肯定选两个选择中的和最大的
 * dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
 * 时间复杂度是 O(N)，空间复杂度也是 O(N)
 * author: hongchen.liao
 * date:  2022/7/25
 */
public class _Offer_42 {

    class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            if(len == 0) return 0;
            int[] dp = new int[len];
            //base case
            //第一个元素前面没有子数组
            dp[0] = nums[0];
            for(int i = 1; i < len;i++){
                dp[i] = Math.max(nums[i] , nums[i] + dp[i-1]);
            }
            int res = Integer.MIN_VALUE;
            for(int i = 0; i < len; i++){
                res = Math.max(res,dp[i]);
            }
            return res;
        }
    }

    class Solution2 {
        public int maxSubArray(int[] nums) {
            int pre = 0, ans = nums[0];
            for(int x : nums){
                pre = Math.max(pre + x, x);
                ans = Math.max(ans, pre);
            }
            return ans;
        }
    }



}
